1. Field of the Invention
The present invention relates to a communications network which transmits packets and contains a plurality of services, and more specifically to an apparatus and method of controlling the cell transfer rate in an ATM (asynchronous transfer mode) network containing a plurality of services such as an ABR (available bit rate) service, a UBR (unspecified bit rate) service, and so on.
2. Description of the Related Art
Currently, in an ATM forum and the ITU-T (International Telecommunication Union-Telecommunication Standardization Sector), an ABR service is considered a method of applying the data switch technology in the ATM to a high-speed data communications network such as a LAN (local area network), a WAN (wide area network), and so on.
To easily accommodate a conventional LAN, a UBR service in which the quality is not defined is also considered.
Described below is the ABR service considered in the ATM forum and the ITU-T.
In the communications using the ABR service, a resource management cell (RM cell) is used to notify a terminal of the information about a network resource. A source terminal transmits an RM cell each time it transmits the predetermined number of user data cells. The RM cell reaches a destination terminal through a network, and is looped back to the source terminal.
On the other hand, an ATM switch in the network notifies the source terminal of the information in the network by writing the resource information (band information and congestion information) in the ATM switch to an RM cell passing through the ATM switch. Upon receipt of the RM cell to which the band information and the congestion information, the source terminal re-computes the allowed cell rate (ACR) according to the information, and transmits the cell at a rate equal to or lower than the ACR.
When the source terminal establishes an ABR connection at the start of the communications, it declares through the network the peak cell rate (PCR), which is the highest transmission rate, and the minimum cell rate (MCR), which is the lowest request rate, and negotiates for their values. As a result of the negotiation, the source terminal cannot transmit a cell at a rate higher than the determined PCR. On the other hand, the network guarantees the source terminal a cell transmission rate equal to or higher than the MCR determined as a result of the negotiation. Accordingly, in the ABR service, the ACR of the source terminal is variable in the range from the MCR to the PCR (MCRxe2x89xa6ACRxe2x89xa6PCR).
Using the ABR service in the above described operation, the network can avoid congestion or recover from the congestion, and the terminal units can transmit cells at a high transmission rate when the resources of the network are available.
Recently, the operations of the source terminal and the destination terminal communicating with each other through the ABR service are considered targets to be standardized in the ATM forum. Described below is the outline of the operations.
FIG. 1A is a chart showing the concept of the flow control in the ABR service.
In FIG. 1A, according to the arrow indicating the forward flow A, an ABR source terminal 101 transmits a cell forward (from source to destination) at a rate equal to or lower than the ACR at each point. At this time, the ABR source terminal 101 transmits one RM cell 114 to a switch (ATM switch) 102 each time a predetermined number of user data cells 112 are transmitted. Upon receipt of an RM cell 114F from the switch 102, the ABR source terminal 101 adds a predetermined value to the value of the ACR if the congestion indicator (CI) bit (not shown in FIG. 1A) in the RM cell 114B is set to 0 (non-congestion), and if the no-increase (NI) bit is set to 0 (not specified). On the other hand, if the above described CI bit is set to 1 (congestion), then the ABR source terminal 101 subtracts the predetermined value from the ACR value. Furthermore, the ABR source terminal 101 compares the value of the explicit cell rate (ER) written in the RM cell with the ACR value obtained in the above described computation after the above described operations, and defines a smaller value as a new ACR. At this time, the ACR value should satisfy MCRxe2x89xa6ACRxe2x89xa6PCR.
In FIG. 1A, according to the arrow indicating the backward flow B, an ABR destination terminal 103 terminates the user data cell 112 transmitted from the source terminal, loops back the received RM cell 114F, and transmits it as the backward (from destination to source) RM cell 114B to the ABR source terminal 101. In this case, if the explicit forward congestion indication (EFCI) bit indicating the congestion in the user data cell 112A received immediately before receiving the RM cell 114F is set to 1, then the ABR destination terminal 103 sets the CI bit in the looped-back RM cell 114F to 1, and the RM cell 114 is transmitted as a backward RM cell 114B after the setting.
Described below is the function of the ATM switch in the ABR service.
The operations of the network for realizing the ABR service, that is, the ATM switch, can be performed in an EFCI mode and an ER mode.
In the EFCI mode, the ATM switch sets the EFCI bit in the user data cell passing through the ATM switch to 1 when congestion exists, and passes the cell.
In the ER mode, the ATM switch computes the ER explicitly indicating the transmission rate to the source terminal based on the resources and the congestion state in the ATM switch, and writes the obtained value to the forward or backward RM cell passing through the ATM switch. At this time, the ATM switch compares the ER value in the RM cell with the ER value computed by the ATM switch itself, and writes a smaller ER value to the RM cell.
In addition to the RM cell transmitted from the source terminal, the ATM switch or the destination terminal can generate an RM cell, and transmit it to the source terminal.
In addition to the above described mode function, the functions referred to as ABR VS/VD (virtual source/virtual destination) are assumed as operations of the ATM switch for realizing the ABR service. When the VS/VD functions are realized, a VD function 122a of looping back upstream the forward RM cell transferred from upstream as a backward RM cell is provided at the upstream of an ATM switch 122 as shown in FIG. 1B. At the downstream of the ATM switch 122 (ABR destination terminal 123), a VS function 122b for generating and terminating an RM cell is provided.
Thus, in the VS/VD functions, when the ATM switch 122 having the VS/VD functions loops back, generates, and terminates an RM cell for an ABR connection, the control loop of the ABR connection is divided (segmented) into a plurality of control loops as shown in FIG. 1B, not a simple loop of an ABR source terminal 121, an ATM switch network, an ABR destination terminal 123, an ATM switch network, and an ABR source terminal 121.
In this case, the VD function 122a provided in the ATM switch 122 virtually simulates the function of a destination terminal. Similarly, the VS function 122b provided in the ATM switch 122 virtually simulates the function of a source terminal.
Thus, the control loop between the ABR source terminal 121 and the ABR destination terminal 123 is divided into a plurality of control loops by the ATM switch 122. In each control loop, the feedback control of the transfer rate using an ER value is performed in parallel so that the response of the feedback can be improved. As a result, the network can more quickly avoid and recover from congestion, and the terminal can communicate cells at a higher rate when the resources of the network are available.
The following functions are required to realize the above described VS/VD functions.
(1) ABR Source/Destination operations prescribed by the ATM forum traffic management 4.0 (essential functions).
a) generating and terminating an RM cell (function to be realized by the VS).
b) computing ACR according to the information set in the received backward RM cell (function to be realized by the VS).
c) transmitting a user data cell from the ACR (function to be realized by the VS).
d) looping back an RM cell, and scheduling an out-rate RM cell (function to be realized by the VD). An out-rate cell refers to a cell to be transmitted with the CLP set to 1 (CLP=1) when the available band of a looped-back line is set to 0 by the ABR control. The out-rate RM cell has a stronger probability that it is discarded in the network than an RM cell whose CLP is set to 0 (CLP=0).
e) setting the CI bit in the looped-back RM cell to 1 when a user data cell whose EFCI bit is set to 1 is received (function to be realized by the VD).
f) generating a backward explicit congestion indicator RM cell (BECN RM cell) (function to be realized by the VD).
(2) transmitting an MCR (essential function)
a) transmitting an MCR in the RM cell received by the VS from downstream (destination terminal) to the upstream (source terminal) VD.
b) transmitting an MCR in the RM cell received by the VD from upstream to the upstream VS.
(3) controlling VS-VD in the same switch (implementation specific).
a) transmitting an ER in the RM cell terminated by the VS to an upstream VD in the switch accommodating the VS.
b) setting ABR parameter for a segment to be supported.
c) computing an ER at a point where congestion arises in the switch.
The above described operations are to be standardized in the ATM forum. However, a concrete control system and implementation method is not to be standardized. For example, the congestion detecting method in the ATM switch or the ER computation algorithm required to realize the function of the above described (c) in (3) are not targets to be standardized.
The RM cell is normally generated by a source terminal, but can be generated by a switch or a destination terminal. In this case, the initial value set in the field in the RM cell may be different from the initial value of the RM cell generated by the source terminal.
FIG. 1C shows the format of an RM cell.
Described below is the outline of each field of the RM cell.
Header
In the RM VCC (virtual channel connection), the PTI (payload type identifier)=110. In the RM VPC (virtual pass connection), PTI=110 and VCI=6.
A payload contains the following fields.
ID: protocol ID
In the ABR, the ID is set to 1.
The seventh octet in the RM cell is referred to as a message type field, and contains the following DIR, BN, CI, NI, RA, and Reserved.
DIR: direction
DIR is set to 0 for forward, and 1 for backward. The xe2x80x98forwardxe2x80x99 refers to the direction of the RM cell flow which is the same as the direction of the user data cell flow. The source terminal transmits the RM cell with the DIR set to 0. The destination terminal transmits the RM cell with the DIR set to 1.
BN: backward explicit congestion notification
BN is used to distinguish a BECN RM cell from the RM cell generated by the source terminal. A switch unit or a destination terminal sets BN to 1, and generates a BECN RM cell. The source terminal sets the BN to 0 and generates an RM cell.
CI: congestion indication
CI is set to 1 for congestion, and 0 for non-congestion. When the CI is set to 1, the source terminal reduces the ACR.
NI: no increase
NI is used to suppress an increase of the ACR value at the source terminal. Unlike the CI, the NI is not used to reduce the ACR.
The NI is used when the switch detects a sign of congestion. Normally, the source terminal sets the NI to 0 and transmits an RM cell. However, the RM cell can be transmitted with the NI set to 1 to indicate that there is no need of increasing the value of the ACR.
RA: request acknowledge
RA is not used at an ABR regulated in the ATM forum. The RA is set to 0 or set according to the ITU-T Recommendation I.371.
ER:
An ER field is set to a value of the ER. The ER is used to limit the ACR of the source terminal to a specific value. The value of the ER is, for example, a value of the PCR requested by the source terminal, etc. as an initial value, and is reduced by a network element such as a switch, and so on.
CCR: current cell rate
A CCR field is set to the value of the ACR of a source terminal when the source terminal transmits a forward RM cell. The value of the ACR set in the CCR field can be used when a switch computes the ER.
MCR: minimum cell rate
An MCR field is set to the value of the MCR negotiated and determined when a call is established. The value set for the MCR field can be used when the switch computes the band. If the value set for the MCR field is different from the MCR determined when a call is established, then the switch can be rewritten to the MCR determined when the call is established.
QL: queue length
A QL field is not used at the ABR regulated in the ATM forum. The QL field is set to 0 or set according to the ITU-T Recommendation I.371.
SN: sequence number
An SN field is not used at the ABR regulated in the ATM forum. The SN field is set to 0 or set according to the ITU-T Recommendation I.371.
CRC-10: cyclic redundancy checkxe2x80x9410
The value of the CRC set in the CRC-10 field is the same as the value of the CRC set in the OAM (operation, administration, and maintenance) cell.
Described next is a method of expressing the rate in each of the above described ER, CCR, and MCR fields in the RM cell.
xe2x80x83R=2e(1+m/512)xc3x97nz(cell/seconds)
As represented by the equation above, the rate of each of the ER, CCR, and MCR fields is expressed by the floating point number representation in binary data specified by a 5-bit exponent (e), a 9-bit mantissa (m), and a 1-bit nonzero flag (nz).
In each of the ER, CCR, and MCR fields, a mantissa is set in the 0 through 8th bits, an exponent is set in the 9th through 13th bits, and a nonzero flag is set in the 14th bit as shown in FIG. 1D. The 15th bit is unused.
The ABR service has been described above. The logical concept of an ATM switch system 130 accommodating a plurality of services such as an ABR service, a UBR service, and so on, is described below by referring to FIG. 1E.
As shown in FIG. 1E, various services such as the CBR (constant bit rate), the rt-VBR (real time variable bit rate), the UBR (unspecified bit rate), and so on, are accommodated in the quality control path. The QCP is a path for guarantee the quality of a group of connections having the same qualities in the ATM switch system 130.
The ATM switch system 130 includes a VPI/VCI conversion unit not shown in FIG. 1E, and a buffer not shown in FIG. 1E provided for each QCP class number which is an identification number used to know which service (QCP class) a cell belongs to. A band assigned to each QCP class is preliminarily assigned based on the physical communications speed of an output line. The descriptions other than the above described components are omitted here.
A cell of each of the above described services is transmitted from a source terminal with a self-routing tag in the ATM switch system 130 assigned by the VCI/VPI conversion unit. A QCP class number is set in the tag. The cell is written to a corresponding buffer according to the QCP class number. The cell written to the buffer is read from the buffer based on the above described band assigned to a corresponding QCP class.
When feedback control is performed in the above described ER mode on the ABR service, the UBR service, and so on, and when the feedback control is performed in the ER mode on a plurality of ABR services in different qualities using the quality controlling function such as the above described QCP, the following problem occurs.
If each of the ABR service, the UBR service, and so on, is accommodated in the control path such as the QCP, and so on, for each quality class, and the ER value of the cell accommodated in the control path is obtained by the ER computation closed in the control path, then an available band for other services cannot be used even if the services are rarely used. As a result, there arises the problem that the entire network resources are not efficiently utilized in some time periods.
On the other hand, if the ER computation is performed on the entire band of the link (internal link) in the ATM switch with the control path such as the QCP, and so on, ignored, then the allowed bands (ER value) for all quality services accommodated in the link are equal, thereby causing the problem that the communications quality of each service cannot be guaranteed.
The present invention aims at providing a cell transfer rate control apparatus and method for efficiently utilizing network resources and guaranteeing the communications quality of each service.
The cell transfer control apparatus according to the first aspect of the present invention which is mentioned in claim 1, includes a quality class buffer, a congestion determination unit, an input rate observation unit, a first load factor computation unit, a second load factor computation unit, a average cell rate computation unit, and an ER computation unit.
In the first phase of the present invention, a plurality of quality class buffers QCP(i) are provided for each quality class i (i=1, 2, . . . , n) to guarantee the communications quality declared by the user. The congestion determination unit determines whether the above described quality class buffer QCP(i) is in the congestion state or in the non-congestion state based on the predetermined first threshold set in the quality class buffer QCP(i). The input rate observation unit observes the input cell rate (BWI_QCP(i)) of each quality class buffer QCP(i), and the input cell rate (BWI_ALL) of the link accommodating the above described quality class buffer QCP(i) in each predetermined observation period. Depending on the determination result from the congestion determination unit, the first load factor computation unit computes the load factor (OLF1_QCP(i)) of the above described quality class buffer QCP(i) in the non-congestion state based on the OLF1_QCP(i)=BWI_QCP(i)/BWO1_QCP(i), which is the ratio of the BWI_QCP(i) of the above described quality class buffer QCP(i) observed by the input rate observation unit to the target output band (BWO1_QCP(i)) in the non-congestion state predetermined for the above described quality class buffer QCP(i), when the quality class buffer QCP(i) is in the non-congestion state. The first load factor computation unit computes the load factor (OLF2_QCP(i)) of the above described quality class buffer QCP(i) in the congestion state based on the OLF2_QCP(i)=BWI_QCP(i)/BWO2_QCP(i), which is the input cell rate (BWI_QCP(i)) of the above described quality class buffer QCP(i) observed by the input rate observation unit to the target output band (BWO2_QCP(i)) in the congestion state predetermined for the above described quality class buffer QCP(i) when the quality class buffer QCP(i) is in the congestion state. Depending on the determination result from the congestion determination unit, the second load factor computation unit computes the load factor (OLF1_ALL) of the link accommodating the above described quality class buffer QCP(i) in the non-congestion state based on the OLF1_ALL=BWI_ALL/BWO1_ALL, which is the ratio of the input cell rate (BWI_ALL) of the above described link observed by the input rate observation unit to the target output band (BWO1_ALL) in the non-congestion state predetermined for the above described link, when the quality class buffer QCP(i) is in the non-congestion state. The second load factor computation unit computes the load factor (OLF2_ALL) of the above described link in the congestion state based on the OLF2_ALL=BWI_ALL/BWO2_ALL, which is the input cell rate (BWI_ALL) of the above described link observed by the input rate observation unit to the target output band (BWO2_ALL) in the congestion state predetermined for the above described link when the quality class buffer QCP(i) is in the congestion state. When a forward RM cell arrives, the average cell rate computation unit computes a new average value (MACR_QCP(i)_NEW) of the CCR of the above described quality class buffer QCP(i) using the CCR_QCP(i) and the MACR_QCP(i)_OLD when the quality class buffer QCP(i) is in the congestion state, and the CCR value (CCR_QCP(i)) set in the CCR field of the above described forward RM cell is smaller than MACR_QCP(i)_OLD, which is an average value of the CCR computed through a predetermined algorithm set in the CCR field of the forward RM cell which previously arrived at the above described quality class buffer QCP(i), or when the quality class buffer QCP(i) is in the non-congestion state, and the CCR value set in the CCR field of the forward RM cell is larger than the MACR_QCP(i)_OLD. The average cell rate computation unit also computes a new average value (MACR_QCP(i)_NEW) of the CCR of the link accommodating the above described quality class buffer QCP(i) based on the CCR value (CCR_ALL) set in the CCR field of the forward RM cell which arrives at the above described link, and the MACR_ALL_OLD, which is an average value of the CCR computed through a predetermined algorithm set in the CCR field of the forward RM cell which previously arrived at the above described link. Depending on the determination result of the above described congestion determination unit, the ER computation unit sets the first explicit cell rate (ER1) to a value obtained by dividing the MACR_QCP(i)_NEW obtained by the above described average cell rate computation unit by the OLF1_QCP(i) obtained by the above described first load factor computation unit, or to a value obtained by dividing the MACR_ALL_NEW obtained by the above described average cell rate computation unit by the OLF_ALL obtained by the second load factor computation unit whichever is larger when the quality class buffer QCP(i) is in the non-congestion state. When the quality class buffer QCP(i) is in the congestion state, the ER computation unit sets the first explicit cell rate (ER1) to a value obtained by dividing the MACR_QCP(i)_NEW obtained by the above described average cell rate computation unit by the OLF2_QCP(i) obtained by the above described first load factor computation unit, or to a value obtained by dividing the MACR_ALL_New obtained by the above described average cell rate computation unit by the OLF_ALL obtained by the second load factor computation unit whichever is larger when the quality class buffer QCP(i) is in the non-congestion state. Furthermore, the ER computation unit sets the second explicit cell rate (ER2) to the above described first explicit cell rate (ER1) or the minimum cell rate set in the connection of the above described quality class buffer QCP(i), whichever is larger.
The cell transfer control apparatus according to the second aspect of the present invention which is mentioned in claim 2, includes a quality class buffer, a congestion determination unit, a target output band computation unit, an input rate observation unit, a load factor computation unit, an average cell rate computation unit, and an ER computation unit.
In the second phase of the present invention, a plurality of quality class buffers QCP(i) are provided for each quality class i (i=1, 2, . . . , n) to guarantee the communications quality declared by the user. The congestion determination unit determines whether the above described quality class buffer QCP(i) is in the congestion state or in the non-congestion state based on the predetermined first threshold set in the quality class buffer QCP(i). Depending on the determination result from the above described congestion determination unit, a target output band computation unit computes a new target output band (BWO_QCP(i)_NEW) of the above described quality class buffer QCP(i) by increasing the current target output band (BWO_QCP(i)_OLD) of the above described quality class buffer QCP(i) when the quality class buffer QCP(i) is in the non-congestion state. The target output band computation unit computes a new target output band (BWO_QCP(i)_NEW) of the above described quality class buffer QCP(i) by decreasing the current target output band (BWO_QCP(i)_OLD) of the above described quality class buffer QCP(i) when the quality class buffer QCP(i) is in the congestion state. The input rate observation unit observes the input cell rate (BWI_QCP(i)) of each quality class buffer QCP(i) for each predetermined observation period. The load factor computation unit computes, for the quality class buffer QCP(i), the load factor (OFL_QCP(i)) of the quality class buffer QCP(i) based on the OLF_QCP(i)=BWI_QCP(i)/BWO_QCP(i)_NEW, which is the ratio of the input cell rate (BWI_QCP(i)) of the quality class buffer QCP(i) observed by the above described input rate observation unit to the target output band (BWO_QCP(i)_NEW) obtained by the target output band computation unit. When a forward RM cell arrives, the average cell rate computation unit computes a new average value (MACR_QCP(i)_NEW) of the CCR of the above described quality class buffer QCP(i) using the CCR_QCP(i) and the MACR_QCP(i)_OLD when the quality class buffer QCP(i) is in the congestion state, and the CCR value (CCR_QCP(i)) set in the CCR field of the above described forward RM cell is smaller than MACR_QCP(i)_OLD, which is an average value of the CCR computed through a predetermined algorithm set in the CCR field of the forward RM cell which previously arrived at the above described quality class buffer QCP(i), or when the quality class buffer QCP(i) is in the non-congestion state, and the CCR value set in the CCR field of the forward RM cell is larger than the MACR_QCP(i)_OLD. The ER computation unit computes the first explicit cell rate (ER1) of the quality class buffer QCP(i) as a ratio of the MACR_QCP(i)_NEW of the above described quality class buffer QCP(i) obtained by the average cell rate computation unit to the OLF_QCP(i) of the quality class buffer QCP(i) obtained by the load factor computation unit, and sets the second explicit cell rate (ER2) to the above described first explicit cell rate (ER1) or the minimum cell rate set for the connection of the quality class buffer QCP(i), whichever is larger.
The cell transfer rate control apparatus according to the third aspect of the present invention which is mentioned in claim 67, includes a storage unit, a determination unit, a observation unit, a load factor computation unit, a link load factor computation unit, an average cell rate computation unit, and an explicit cell rate computation unit.
In the third phase of the present invention, a plurality of storage units store cells. The determination unit determines a congestion state if the number of cells stored in the storage unit is equal to or larger than a predetermined value, or a non-congestion state if it is smaller than the predetermined threshold. The observation unit observes the input cell rate of the storage unit and the link input cell rate in the ATM switch accommodating the storage unit. The load factor computation unit computes the load factor of the storage unit, which is the ratio of the input cell rate of the storage unit observed by the observation unit to the target output band of the storage unit, in each of the congestion state and the non-congestion state determined by the determination unit. The link load factor computation unit computes the link load factor of the above described link, which is the ratio of the link input cell rate of the link observed by the observation unit to the link target output band of the above described link, in each of the congestion state and the non-congestion state determined by the determination unit. The average cell rate computation unit computes an average value of the current cell rate of a resource management cell in the storage unit and the link if the determination unit determines a congestion state when a forward resource management cell arrives, and the current cell rate of the resource management cell is smaller than an average value, or if the determination unit determines a non-congestion state, and the current cell rate of the resource management cell is larger than the average value. When the determination unit determines a non-congestion, the explicit cell rate computation unit computes, as the first explicit cell rate, the value by dividing the average value of the current cell rate computed by the average cell rate computation unit and stored in the storage unit by the above described load factor computed by the load factor computation unit, or the value obtained by dividing the average value of the above described current cell rate computed by the average cell rate computation unit and stored in the link by the link load factor computed by the link load factor computation unit, whichever is larger.
The cell transfer rate control apparatus according to the fourth aspect of the present invention which is mentioned in claim 68, includes the storage unit, the determination unit, the target output band computation unit, the observation unit, the load factor computation unit, the average cell rate computation unit, and the explicit cell rate computation unit.
In the fourth phase of the present invention, a plurality of storage units store cells. The determination unit determines a congestion state if the number of cells stored in the storage unit is equal to or larger than a predetermined value, or a non-congestion state if it is smaller than the predetermined threshold. The target output band computation unit computes a target output band by increasing the target output band of the storage unit when the determination unit determines a non-congestion state, or the target output band by decreasing the target output band of the storage unit when the determination unit determines a congestion state. The observation unit observes the input cell rate of the storage unit. The load factor computation unit computes the load factor of the storage unit, which is the ratio of the above described input cell rate observed by the observation unit and stored in the storage unit to the above described target output band computed by the target output band computation unit. The average cell rate computation unit computes the average value of the current cell rate of a resource management cell when the determination unit determines a congestion state and the current cell rate of the resource management cell is smaller than an average value, or when the determination unit determines a non-congestion state and the current cell rate of the resource management cell is larger than the average value. The explicit cell rate computation unit computes, as the first explicit cell rate, a value by dividing the average value of the current cell rate computed by the average cell rate computation unit by the above described load factor computed by the load factor computation unit, and computes, as the second explicit cell rate, the first explicit cell rate or the minimum cell rate in the storage unit, whichever is larger.